/*
 * @lc app=leetcode.cn id=763 lang=javascript
 *
 * [763] 划分字母区间
 */

// @lc code=start
/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function (S) {
  const lastIdx = new Array(26)
  const size = S.length
  const codeA = 'a'.charCodeAt(0)
  // 获取同一个字母的最后出现的下标
  for (let i = 0; i < size; i++) {
    const currCode = S.charCodeAt(i)
    lastIdx[currCode - codeA] = i
  }

  const rec = []
  let start = 0, end = 0
  // 划分字符串
  for (let i = 0; i < size; i++) {
    const currCode = S.charCodeAt(i)
    end = Math.max(end, lastIdx[currCode - codeA])

    if (i === end) {
      rec.push(end - start + 1)
      start = end + 1
    }
  }

  return rec
};
// @lc code=end

/**
 * 时间复杂度：O(n)，其中 n 是字符串的长度。需要遍历字符串两次，第一次遍历时记录每个字母最后一次出现的下标位置，第二次遍历时进行字符串的划分
 * 空间复杂度：O(Σ)，其中 Σ 是字符串中的字符集大小。这道题中，字符串只包含小写字母，因此 Σ=26
 */